package com.lee.algorithm.sort;

import static com.lee.algorithm.sort.SortUtil.print;
import static com.lee.algorithm.sort.SortUtil.swap;

/***
 * @description: 堆排序
 *      堆是完全二叉树，分大顶堆、小顶堆
 *      i的左孩子：2*i+1，i的右孩子：2*i+2，i的父：(i-1)/2
 *
 *      求升序用大顶堆，求降序用小顶堆
 *
 *      堆比堆排序要重要！！！
 * @author : 青石路
 * @date: 2021/11/22 20:02
 */
public class HeapSort {

    public static void main(String[] args) {
        // int[] arr = new int[]{9,8,3,2,6,4,5,0,1,1,1};
        int[] arr = new int[]{1,2,3,4,5,6,7,3,2,8};
        heapSort(arr);
        print(arr);
    }

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        int heapSize = arr.length;

        // 构建最初的大顶堆
        /*for (int i = 0; i < heapSize; i++) {
            heapInsert(arr, i);
        }*/

        // 构建最初的大顶堆 优化处理
        // 只需要处理非叶子节点
        for(int i=heapSize/2-1; i>=0; i--) {
            // 将初始数组看成一个普通的堆，从下至上、从右至左 对每个非叶子节点进行堆化
            heapify(arr, i, heapSize);
        }

        /*swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }*/
    }

    /**
     * 堆化过程
     *      某个数在index位置，能否往下移动
     * @param arr
     * @param index
     * @param heapSize
     */
    public static void heapify(int[] arr, int index, int heapSize) {
        // index 左孩子下标
        int left = index * 2 + 1;

        // index 下方还有孩子
        while(left < heapSize) {
            // 两个孩子中，谁的值大，把下标给 largest（left + 1是右孩子的下标）
            int largest = (left + 1 < heapSize) && arr[left+1] > arr[left] ? left+1 : left;

            // 父和较大的孩子之间，谁的值大，把下标给 largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    /**
     * 某个数现在处于index位置，往上继续移动
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        while(arr[index] > arr[(index-1)/2]) {
            swap(arr, index, (index-1)/2);
            index = (index-1)/2;
        }
    }
}
